package oct2013.linkednode;

/**
 * @author Yinzi Chen
 * @date Nov 16, 2013
 */
public class SortList {

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode cur = head, end = head, prev = null;
        while (end != null && end.next != null) {
            prev = cur;
            cur = cur.next;
            end = end.next.next;
        }
        prev.next = null;
        return merge(sortList(head), sortList(cur));
    }

    ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        while (l1 != null) {
            cur.next = l1;
            l1 = l1.next;
            cur = cur.next;
        }
        while (l2 != null) {
            cur.next = l2;
            l2 = l2.next;
            cur = cur.next;
        }
        return dummy.next;
    }

}
